/**
 * Copyright (C) 2007 Stefan Buettcher. All rights reserved.
 * This is free software with ABSOLUTELY NO WARRANTY.
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
 * 02111-1307, USA
 **/

/**
 * Implementation of the XPath basic functions.
 *
 * author: Stefan Buettcher
 * created: 2004-11-30
 * changed: 2006-09-19
 **/


#include <math.h>
#include <stdio.h>
#include <string.h>
#include "xpath_primitives.h"
#include "getquery.h"
#include "../misc/all.h"
#include "../filters/inputstream.h"


#define XPATH_EPSILON (1.0E-10)


XMLElementList * XPath_createElementList(int length, offset *from, offset *to, int32_t *level) {
	XMLElementList *result = (XMLElementList*)malloc(sizeof(XMLElementList));
	result->length = length;
	result->from = from;
	result->to = to;
	result->level = level;
	result->score = NULL;
	return result;
} // end of XPath_createElementList(int, offset*, offset*)


XMLElementList * XPath_createElementList(int length, offset *from, offset *to, int32_t *level, double *score) {
	XMLElementList *result = (XMLElementList*)malloc(sizeof(XMLElementList));
	result->length = length;
	result->from = from;
	result->to = to;
	result->level = level;
	result->score = score;
	return result;
} // end of XPath_createElementList(int, offset*, offset*, double*)


void XPath_increaseElementListLength(XMLElementList *list, int newLength) {
	assert(newLength > list->length);
	list->length = newLength;
	list->from = (offset*)realloc(list->from, newLength * sizeof(offset));
	list->to = (offset*)realloc(list->to, newLength * sizeof(offset));
	list->level = (int32_t*)realloc(list->level, newLength * sizeof(int32_t));
	if (list->score != NULL)
		list->score = (double*)realloc(list->score, newLength * sizeof(double));
} // end of XPath_increaseElementListLength(XMLElementList*, int)


XMLElementList * XPath_duplicateElementList(XMLElementList *list) {
	XMLElementList *result = (XMLElementList*)malloc(sizeof(XMLElementList));
	int length = list->length;
	result->length = length;
	result->from = (offset*)malloc(length * sizeof(offset));
	memcpy(result->from, list->from, length * sizeof(offset));
	result->to = (offset*)malloc(length * sizeof(offset));
	memcpy(result->to, list->to, length * sizeof(offset));
	result->level = (int32_t*)malloc(length * sizeof(int32_t));
	memcpy(result->level, list->level, length * sizeof(int32_t));
	if (list->score == NULL)
		result->score = NULL;
	else {
		result->score = (double*)malloc(length * sizeof(double));
		memcpy(result->score, list->score, length * sizeof(double));
	}
	return result;
} // end of XPath_duplicateElementList(XMLElementList*)


void XPath_deleteElementList(XMLElementList *elementList) {
	free(elementList->from);
	free(elementList->to);
	if (elementList->level != NULL) {
		free(elementList->level);
		elementList->level = NULL;
	}
	if (elementList->score != NULL) {
		free(elementList->score);
		elementList->score = NULL;
	}
	free(elementList);
} // end of XPath_deleteElementList(XMLElementList*)


typedef struct {
	XMLElementList *list;
	int listPosition;
} XMLElementListHeapNode;


static void XPath_mergeElementLists_moveHeapNodeUp(XMLElementListHeapNode *heap, int node) {
	int pos = heap[node].listPosition;
	if (pos >= heap[node].list->length)
		return;
	offset thisStart = heap[node].list->from[pos];
	offset parentStart;
	while (node > 0) {
		int parent = (node - 1) / 2;
		pos = heap[parent].listPosition;
		if (pos >= heap[parent].list->length)
			parentStart = MAX_OFFSET;
		else
			parentStart = heap[parent].list->from[pos];
		if (parentStart <= thisStart)
			break;
		XMLElementListHeapNode swapper = heap[node];
		heap[node] = heap[parent];
		heap[parent] = swapper;
		node = parent;
	}
} // end of XPath_mergeElementLists_moveHeapNodeUp(XMLElementListHeapNode*, int)


static void XPath_mergeElementLists_moveHeapNodeDown(
		XMLElementListHeapNode *heap, int node, int heapSize) {
	int pos = heap[node].listPosition;
	offset thisStart = MAX_OFFSET;
	if (pos < heap[node].list->length)
		thisStart = heap[node].list->from[pos];
	int leftChild = node * 2 + 1;
	int rightChild = node * 2 + 2;
	while (leftChild < heapSize) {
		int child = leftChild;
		offset childStart = MAX_OFFSET;
		if (heap[child].listPosition < heap[child].list->length)
			childStart = heap[child].list->from[heap[child].listPosition];
		if (rightChild < heapSize)
			if (heap[rightChild].listPosition < heap[rightChild].list->length) {
				offset rightChildStart = heap[rightChild].list->from[heap[rightChild].listPosition];
				if (rightChildStart < childStart) {
					child = rightChild;
					childStart = rightChildStart;
				}
			}
		if (thisStart < childStart)
			break;
		XMLElementListHeapNode swapper = heap[node];
		heap[node] = heap[child];
		heap[child] = swapper;
		node = child;
		leftChild = node * 2 + 1;
		rightChild = node * 2 + 2;
	}
} // end of XPath_mergeElementLists_moveHeapNodeDown(XMLElementListHeapNode*, int, int)


XMLElementList * XPath_mergeElementLists(XMLElementList **inputLists, int listCnt) {
	int heapSize = listCnt;
	XMLElementListHeapNode *heap =
		typed_malloc(XMLElementListHeapNode, (heapSize > 0 ? heapSize : 1));
	int resultLength = 0;
	bool useScore = false;
	for (int i = 0; i < heapSize; i++) {
		heap[i].list = inputLists[i];
		heap[i].listPosition = 0;
		resultLength += heap[i].list->length;
		if (heap[i].list->score != NULL)
			useScore = true;
		XPath_mergeElementLists_moveHeapNodeUp(heap, i);
	}
	XMLElementList *result = (XMLElementList*)malloc(sizeof(XMLElementList));
	result->length = resultLength;
	result->from = typed_malloc(offset, (resultLength > 0 ? resultLength : 1));
	result->to = typed_malloc(offset, (resultLength > 0 ? resultLength : 1));
	result->level = typed_malloc(int32_t, (resultLength > 0 ? resultLength : 1));
	if (useScore)
		result->score = typed_malloc(double, (resultLength > 0 ? resultLength : 1));
	else
		result->score = NULL;
	int outCnt = 0;
	for (int i = 0; i < resultLength; i++) {
		XMLElementList *headOfHeap = heap[0].list;
		int pos = heap[0].listPosition;
		result->from[outCnt] = headOfHeap->from[pos];
		result->to[outCnt] = headOfHeap->to[pos];
		result->level[outCnt] = headOfHeap->level[pos];
		if (useScore) {
			if (headOfHeap->score != NULL)
				result->score[outCnt] = headOfHeap->score[pos];
			else
				result->score[outCnt] = 1.0;
		}
		if (outCnt > 0)
			if (result->from[outCnt - 1] == result->from[outCnt])
				if (result->to[outCnt - 1] == result->to[outCnt]) {
					if (result->score != NULL)
						result->score[outCnt - 1] += result->score[outCnt];
					outCnt--;
				}
		outCnt++;
		heap[0].listPosition++;
		XPath_mergeElementLists_moveHeapNodeDown(heap, 0, heapSize);
	}
	free(heap);
	result->length = outCnt;
	return result;
} // end of XPath_mergeElementLists(XMLElementList**, int)


typedef struct {
	offset from, to;
	int32_t level;
	double score;
} ScoredElement;

static void XPath_mergeSortElemList(ScoredElement *list, int length, int sortOrder) {
	if (length <= 5) {
		for (int j = 0; j < length; j++) {
			int best = j;
			if (sortOrder == XPATH_DOCUMENT_ORDER) {
				for (int k = j + 1; k < length; k++)
					if (list[k].from < list[best].from)
						best = k;
			}
			else {
				for (int k = j + 1; k < length; k++)
					if (list[k].from > list[best].from)
						best = k;
			}
			ScoredElement swapper = list[best];
			list[best] = list[j];
			list[j] = swapper;
		}
	}
	else {
		int half = length / 2;
		XPath_mergeSortElemList(list, half, sortOrder);
		XPath_mergeSortElemList(&list[half], length - half, sortOrder);
		ScoredElement *temp = typed_malloc(ScoredElement, length);
		int outPos = 0;
		int leftPos = 0;
		int rightPos = half;
		if (sortOrder == XPATH_DOCUMENT_ORDER) {
			while (true) {
				if (list[leftPos].from < list[rightPos].from) {
					temp[outPos++] = list[leftPos++];
					if (leftPos >= half)
						break;
				}
				else {
					temp[outPos++] = list[rightPos++];
					if (rightPos >= length)
						break;
				}
			}
		} // end if (sortOrder == XPATH_DOCUMENT_ORDER)
		else {
			while (true) {
				if (list[leftPos].from > list[rightPos].from) {
					temp[outPos++] = list[leftPos++];
					if (leftPos >= half)
						break;
				}
				else {
					temp[outPos++] = list[rightPos++];
					if (rightPos >= length)
						break;
				}
			}
		} // end else
		while (leftPos < half)
			temp[outPos++] = list[leftPos++];
		while (rightPos < length)
			temp[outPos++] = list[rightPos++];
		memcpy(list, temp, sizeof(ScoredElement) * length);
		free(temp);
	}
} // end of XPath_mergeSortElemList(XMLElementList*, int, int, int)


void XPath_sortElementList(XMLElementList *list, int sortOrder) {
	if (list->length <= 1)
		return;
	ScoredElement *sortList = typed_malloc(ScoredElement, list->length);
	for (int i = list->length - 1; i >= 0; i--) {
		sortList[i].from = list->from[i];
		sortList[i].to = list->to[i];
		sortList[i].level = list->level[i];
		if (list->score != NULL)
			sortList[i].score = list->score[i];
	}
	XPath_mergeSortElemList(sortList, list->length, sortOrder);
	int outCount = 0;
	int length = list->length;
	for (int i = 0; i < length; i++) {
		list->from[outCount] = sortList[i].from;
		list->to[outCount] = sortList[i].to;
		list->level[outCount] = sortList[i].level;
		if (list->score != NULL)
			list->score[outCount] = sortList[i].score;
		if (outCount > 0)
			if (list->from[outCount - 1] == list->from[i])
				if (list->to[outCount - 1] == list->to[i]) {
					if (list->score != NULL)
						list->score[outCount - 1] += list->score[outCount];
					outCount--;
				}
		outCount++;
	}
	list->length = outCount;
	free(sortList);
} // end of XPath_sortElementList(XMLElementList*, int)


XPathData * XPath_createXPathData(Index *index, char *stringValue) {
	XPathData *result = (XPathData*)malloc(sizeof(XPathData));
	result->index = index;
	result->dataType = XPATH_STRING;
	result->stringValue = stringValue;
	return result;
} // end of XPath_createXPathData(Index*, char*)


XPathData * XPath_createXPathData(Index *index, double numberValue) {
	XPathData *result = (XPathData*)malloc(sizeof(XPathData));
	result->index = index;
	result->dataType = XPATH_NUMBER;
	result->numberValue = numberValue;
	return result;
} // end of XPath_createXPathData(Index*, double)


XPathData * XPath_createXPathData(Index *index, bool booleanValue) {
	XPathData *result = (XPathData*)malloc(sizeof(XPathData));
	result->index = index;
	result->dataType = XPATH_BOOLEAN;
	result->booleanValue = booleanValue;
	return result;
} // end of XPath_createXPathData(Index*, bool)


void XPath_deleteXPathData(XPathData *data) {
	switch (data->dataType) {
		case XPATH_NODESET:
			XPath_deleteElementList(data->nodeValue);
			break;
		case XPATH_STRING:
			free(data->stringValue);
			break;
	}
	free(data);
} // end of XPath_deleteXPathData(XPathData*)


/** Adds the offset given by "off" to the string given by "string". **/
static void strcatOffset(char *string, offset off) {
	int lower = off % 1000000000;
	int upper = off / 1000000000;
	if (upper == 0)
		sprintf(&string[strlen(string)], "%i", lower);
	else
		sprintf(&string[strlen(string)], "%i%09i", upper, lower);
} // end of strcatOffset(char*, offset)


char * XPath_getElement(Index *index, offset from, offset to) {
	char arguments[64];
	arguments[0] = 0;
	strcatOffset(arguments, from);
	strcat(arguments, " ");
	strcatOffset(arguments, to);
	GetQuery *gq =
		new GetQuery(index, "get", EMPTY_MODIFIERS, arguments, Index::GOD, -1);
	gq->parse();
	char *result = (char*)malloc(4096);
	int resultAllocated = 4096;
	int resultLength = 0;
	char *line = (char*)malloc(FilteredInputStream::MAX_FILTERED_RANGE_SIZE);
	int lineLength = 0;
	while (gq->getNextLine(line)) {
		lineLength = strlen(line);
		if (lineLength + resultLength + 1 > resultAllocated) {
			resultAllocated = ((lineLength + resultLength + 1) * 3) / 2;
			result = (char*)realloc(result, resultAllocated);
		}
		strcpy(&result[resultLength], line);
		resultLength += lineLength;
	}
	free(line);
	delete gq;
	return result;
} // end of XPath_getElement(Index*, offset, offset)


/**
 * XPath_getText returns all TEXT that belongs to the element starting at
 * "from" and ending at "to". The "level" informatio is needed to exclude
 * child elements.
 **/
char * XPath_getText(Index *index, offset from, offset to, int level) {
	offset start, end;
	char openTag[32], closeTag[32];
	sprintf(openTag, "<level!%i>", level + 1);
	sprintf(closeTag, "</level!%i>", level + 1);
	ExtentList *openList = index->getPostings(openTag, Index::GOD);
	ExtentList *closeList = index->getPostings(closeTag, Index::GOD);
	offset position = from + 1;
	char *result = duplicateString("");
	int resultLength = 0;
	while (position < to) {
		offset continueUntil = to;
		if (openList->getFirstStartBiggerEq(position, &start, &end))
			if (start <= continueUntil)
				continueUntil = start - 1;
		if (continueUntil >= position) {
			char *string = XPath_getElement(index, position, continueUntil);
			int stringLength = strlen(string);
			result = (char*)realloc(result, resultLength + stringLength + 2);
			strcpy(&result[resultLength], string);
			free(string);
			resultLength += stringLength;
		}
		if (closeList->getFirstStartBiggerEq(start, &start, &end))
			position = end + 1;
		else
			position = MAX_OFFSET;
	}
	delete openList;
	delete closeList;
	return result;
} // end of XPath_getText(Index*, offset, offset)


char * XPath_extractString(XPathData *argument) {
	if (argument->dataType == XPATH_STRING)
		return duplicateString(argument->stringValue);
	else {
		XPathData *dummy = XPath_string(argument);
		char *result = duplicateString(dummy->stringValue);
		XPath_deleteXPathData(dummy);
		return result;
	}
} // end of XPath_extractString(XPathData*)


double XPath_extractNumber(XPathData *argument) {
	if (argument->dataType == XPATH_NUMBER)
		return argument->numberValue;
	else {
		XPathData *dummy = XPath_number(argument);
		double result = dummy->numberValue;
		XPath_deleteXPathData(dummy);
		return result;
	}
} // end of extractNumber(XPathData*)


XPathData * XPath_string(XPathData *argument) {
	XPathData *result = (XPathData*)malloc(sizeof(XPathData));
	result->dataType = XPATH_STRING;
	result->index = argument->index;
	switch (argument->dataType) {
		case XPATH_NODESET:
			if (argument->nodeValue->length == 0) {
				// node set is empty: return empty string
				result->stringValue = duplicateString("");
			}
			else {
				// node set is non-empty: return string representation of first node
				result->stringValue = XPath_getText(argument->index,
						argument->nodeValue->from[0], argument->nodeValue->to[0], argument->nodeValue->level[0]);
			}
			break;
		case XPATH_STRING:
			result->stringValue = duplicateString(argument->stringValue);
			break;
		case XPATH_BOOLEAN:
			if (argument->booleanValue)
				result->stringValue = duplicateString("true");
			else
				result->stringValue = duplicateString("false");
			break;
		case XPATH_NUMBER:
			if (isNAN(argument->numberValue))
				result->stringValue = duplicateString("NaN");
			else if (isINF(argument->numberValue))
				result->stringValue = duplicateString("Infinity");
			else if (fabs(argument->numberValue) <= XPATH_EPSILON)
				result->stringValue = duplicateString("0");
			else if (fabs(argument->numberValue - argument->numberValue) <= XPATH_EPSILON) {
				// if the number is an integer, return the integer representation
				char number[64];
				sprintf(number, "%.0lf", argument->numberValue);
				result->stringValue = duplicateString(number);
			}
			else {
				// otherwise, print the decimal "." representation of the number
				char number[64];
				sprintf(number, "%.9lf", argument->numberValue);
				int len = strlen(number);
				while ((number[len - 1] == '0') && (number[len - 2] != '.')) {
					if (--len == 3)
						break;
				}
				number[len] = 0;
				result->stringValue = duplicateString(number);
			}
			break;
		default:
			result->stringValue = duplicateString("");
			result->dataType = XPATH_TYPE_ERROR;
			break;
	}
	return result;
} // end of XPath_string(XPathData*)


XPathData * XPath_concat(XPathData **arguments) {
	Index *index = arguments[0]->index;
	char *resultString = duplicateString("");
	for (int i = 0; arguments[i] != NULL; i++) {
		if (arguments[i]->dataType == XPATH_STRING) {
			char *newString = concatenateStrings(resultString, arguments[i]->stringValue);
			free(resultString);
			resultString = newString;
		}
		else {
			XPathData *dummy = XPath_string(arguments[i]);
			char *newString = concatenateStrings(resultString, dummy->stringValue);
			XPath_deleteXPathData(dummy);
			free(resultString);
			resultString = newString;
		}
	}
	return XPath_createXPathData(index, resultString);
} // end of XPath_concat(XPathData**)


XPathData * XPath_starts_with(XPathData *argument1, XPathData *argument2) {
	char *s1 = XPath_extractString(argument1);
	char *s2 = XPath_extractString(argument2);
	bool result = (strstr(s1, s2) == s1);
	free(s1);
	free(s2);
	return XPath_createXPathData(argument1->index, result);
} // end of XPath_starts_with(XPathData*, XPathData*)


XPathData * XPath_contains(XPathData *argument1, XPathData *argument2) {
	char *s1 = XPath_extractString(argument1);
	char *s2 = XPath_extractString(argument2);
	bool result = (strstr(s1, s2) != NULL);
	free(s1);
	free(s2);
	return XPath_createXPathData(argument1->index, result);
} // end of XPath_contains(XPathData*, XPathData*)


XPathData * XPath_substring_before(XPathData *argument1, XPathData *argument2) {
	char *s1 = XPath_extractString(argument1);
	char *s2 = XPath_extractString(argument2);
	char *match = strstr(s1, s2);
	if (match == NULL)
		s1[0] = 0;
	else
		match[0] = 0;
	free(s2);
	return XPath_createXPathData(argument1->index, s1);
} // end of XPath_substring_before(XPathData*, XPathData*)


XPathData * XPath_substring_after(XPathData *argument1, XPathData *argument2) {
	char *s1 = XPath_extractString(argument1);
	char *s2 = XPath_extractString(argument2);
	char *match = strstr(s1, s2);
	char *result;
	if (match == NULL)
		result = duplicateString("");
	else
		result = duplicateString(&match[strlen(s2)]);
	free(s1);
	free(s2);
	return XPath_createXPathData(argument1->index, result);
} // end of XPath_substring_after(XPathData*, XPathData*)


XPathData * XPath_substring(XPathData *argument, int startPosition, int length) {
	char *s = XPath_extractString(argument);
	int sLen = strlen(s);
	if ((startPosition >= sLen) || (startPosition < 0)) {
		free(s);
		return XPath_createXPathData(argument->index, duplicateString(""));
	}
	else if (startPosition == 0) {
		if (length <= sLen)
			s[length] = 0;
		return XPath_createXPathData(argument->index, s);
	}
	else {
		int pos = startPosition;
		while ((s[pos] != 0) && (pos < startPosition + length)) {
			s[pos - startPosition] = s[pos];
			pos++;
		}
		s[pos - startPosition] = 0;
		return XPath_createXPathData(argument->index, s);
	}
} // end of XPath_substring(XPathData*, int, int)


XPathData * XPath_string_length(XPathData *argument) {
	double result;
	if (argument->dataType == XPATH_STRING)
		result = strlen(argument->stringValue);
	else {
		char *s = XPath_extractString(argument);
		result = strlen(s);
		free(s);
	}
	return XPath_createXPathData(argument->index, result);
} // end of XPath_string_length(XPathData*)


XPathData * XPath_normalize_space(XPathData *argument) {
	char *s = XPath_extractString(argument);
	int inPos = 0;
	int outPos = 0;
	while ((s[inPos] > 0) && (s[inPos] <= ' '))
		inPos++;
	while (s[inPos] != 0) {
		char c = s[inPos];
		s[outPos++] = s[inPos++];
		if ((c > 0) && (c <= ' ')) {
			while ((s[inPos] > 0) && (s[inPos] <= ' '))
				inPos++;
		}
	}
	s[outPos] = 0;
	if (outPos > 0) {
		if ((s[outPos - 1] > 0) && (s[outPos - 1] <= ' '))
			s[--outPos] = 0;
	}
	return XPath_createXPathData(argument->index, s);
} // end of XPath_normalize_space(XPathData*)


XPathData * XPath_translate(XPathData *argument, XPathData *from, XPathData *to) {
	char *string = XPath_extractString(argument);
	char *fromString = XPath_extractString(from);
	char *toString = XPath_extractString(to);
	byte translation[256];
	memset(translation, 0, 256);
	for (int i = 0; (fromString[i] != 0) && (toString[i] != 0); i++) {
		byte a = (byte)fromString[i];
		byte b = (byte)toString[i];
		translation[a] = b;
	}
	free(fromString);
	free(toString);
	int inPos = 0;
	int outPos = 0;
	while (string[inPos] != 0) {
		byte b = (byte)string[inPos++];
		if (translation[b] != 0)
			string[outPos++] = (char)translation[b];
	}
	string[outPos] = 0;
	return XPath_createXPathData(argument->index, string);
} // end of XPath_translate(XPathData*, XPathData*, XPathData*)


XPathData * XPath_boolean(XPathData *argument) {
	bool result;
	switch (argument->dataType) {
		case XPATH_STRING:
			result = (strlen(argument->stringValue) > 0);
			break;
		case XPATH_BOOLEAN:
			result = argument->booleanValue;
			break;
		case XPATH_NUMBER:
			if ((fabs(argument->numberValue) >= XPATH_EPSILON) && (!isNAN(argument->numberValue)))
				result = true;
			else
				result = false;
			break;
		case XPATH_NODESET:
			result = (argument->nodeValue->length > 0);
			break;
		case XPATH_TYPE_ERROR:
			result = false;
			break;
	}
	return XPath_createXPathData(argument->index, result);
} // end of XPath_boolean(XPathData*)


XPathData * XPath_not(XPathData *argument) {
	XPathData *result = XPath_boolean(argument);
	result->booleanValue = !(result->booleanValue);
	return result;
} // end of XPath_not(XPathData*)


XPathData * XPath_true(Index *index) {
	return XPath_createXPathData(index, true);
} // end of XPath_true()


XPathData * XPath_false(Index *index) {
	return XPath_createXPathData(index, false);
} // end of XPath_false()


XPathData * XPath_number(XPathData *argument) {
	char *s;
	double result;
	switch (argument->dataType) {
		case XPATH_STRING:
			if (sscanf(argument->stringValue, "%lf", &result) != 1)
				result = 0; // NAN;
			break;
		case XPATH_BOOLEAN:
			if (argument->booleanValue)
				result = 1.0;
			else
				result = 0.0;
			break;
		case XPATH_NUMBER:
			result = argument->numberValue;
			break;
		case XPATH_NODESET:
			s = XPath_extractString(argument);
			if (sscanf(argument->stringValue, "%lf", &result) != 1)
				result = 0; // NAN;
			free(s);
			break;
		default:
			result = 0; // NAN;
			break;
	}
	return XPath_createXPathData(argument->index, result);
} // end of XPath_number(XPathData*)


XPathData * XPath_sum(XPathData **arguments) {
	double result = 0.0;
	for (int i = 0; arguments[i] != NULL; i++) {
		if (arguments[i]->dataType == XPATH_NUMBER)
			result += arguments[i]->numberValue;
		else {
			double number = XPath_extractNumber(arguments[i]);
			result += number;
		}
	}
	return XPath_createXPathData(arguments[0]->index, result);
} // end of XPath_sum(XPathData**)


XPathData * XPath_floor(XPathData *argument) {
	double number;
	if (argument->dataType == XPATH_NUMBER)
		number = argument->numberValue;
	else
		number = XPath_extractNumber(argument);
	return XPath_createXPathData(argument->index, floor(number));
} // end of XPath_floor(XPathData*)


XPathData * XPath_ceiling(XPathData *argument) {
	double number;
	if (argument->dataType == XPATH_NUMBER)
		number = argument->numberValue;
	else
		number = XPath_extractNumber(argument);
	return XPath_createXPathData(argument->index, ceil(number));
} // end of XPath_ceiling(XPathData*)


XPathData * XPath_round(XPathData *argument) {
	double number;
	if (argument->dataType == XPATH_NUMBER)
		number = argument->numberValue;
	else
		number = XPath_extractNumber(argument);
	return XPath_createXPathData(argument->index, 1.0 * LROUND(number));
} // end of XPath_round(XPathData*)


XPathData * XPath_product(XPathData **arguments) {
	double result = 1.0;
	for (int i = 0; arguments[i] != NULL; i++) {
		if (arguments[i]->dataType == XPATH_NUMBER)
			result *= arguments[i]->numberValue;
		else {
			double number = XPath_extractNumber(arguments[i]);
			result *= number;
		}
	}
	return XPath_createXPathData(arguments[0]->index, result);
} // end of XPath_product(XPathData**)


XPathData * XPath_difference(XPathData **arguments) {
	double result = XPath_extractNumber(arguments[0]);
	for (int i = 1; arguments[i] != NULL; i++) {
		if (arguments[i]->dataType == XPATH_NUMBER)
			result -= arguments[i]->numberValue;
		else {
			double number = XPath_extractNumber(arguments[i]);
			result -= number;
		}
	}
	return XPath_createXPathData(arguments[0]->index, result);
} // end of XPath_difference(XPathData**)


XPathData * XPath_division(XPathData **arguments) {
	double result = XPath_extractNumber(arguments[0]);
	for (int i = 1; arguments[i] != NULL; i++) {
		double number = XPath_extractNumber(arguments[i]);
		if (number == 0.0) {
			result = 0; // NAN;
			break;
		}
		else
			result /= number;
	}
	return XPath_createXPathData(arguments[0]->index, result);
} // end of XPath_division(XPathData**)


XPathData * XPath_modulo(XPathData **arguments) {
	int result = (int)LROUND(XPath_extractNumber(arguments[0]));
	for (int i = 1; arguments[i] != NULL; i++) {
		double number = XPath_extractNumber(arguments[i]);
		int i = (int)LROUND(number);
		if (i == 0) {
			result = 0;
			break;
		}
		else
			result %= i;
	}
	double resultValue = result;
	return XPath_createXPathData(arguments[0]->index, resultValue);
} // end of XPath_modulo(XPathData**)


XPathData * XPath_compare(XPathData *argument1, XPathData *argument2, int comparison) {
	Index *index = argument1->index;
	bool result;

	// first type of comparison: node-set <> node-set
	if ((argument1->dataType == XPATH_NODESET) && (argument2->dataType == XPATH_NODESET)) {
		int length1 = argument1->nodeValue->length;
		char **strings1 = (char**)malloc(length1 * sizeof(char*));
		for (int i = 0; i < length1; i++)
			strings1[i] = NULL;
		int length2 = argument2->nodeValue->length;
		char **strings2 = (char**)malloc(length2 * sizeof(char*));
		for (int i = 0; i < length2; i++)
			strings2[i] = NULL;
		bool found = false;
		for (int j = 0; (j < length1) && (!found); j++) {
			if (strings1[j] == NULL)
				strings1[j] = XPath_getText(index, argument1->nodeValue->from[j],
						argument1->nodeValue->to[j], argument1->nodeValue->level[j]);
			for (int k = 0; (k < length2) && (!found); k++) {
				if (strings2[k] == NULL)
					strings2[k] = XPath_getText(index, argument2->nodeValue->from[k],
							argument2->nodeValue->to[k], argument2->nodeValue->level[k]);
				if (XPath_compare(strings1[j], strings2[k], comparison))
					found = true;
			}
		}
		for (int i = 0; i < length1; i++)
			if (strings1[i] != NULL)
				free(strings1[i]);
		free(strings1);
		for (int i = 0; i < length2; i++)
			if (strings2[i] != NULL)
				free(strings2[i]);
		free(strings2);
		result = found;
	} // end if ((argument1->dataType == XPATH_NODESET) && (argument2->dataType == XPATH_NODESET))

	// second type of comparison: node-set <> anything else
	else if ((argument1->dataType == XPATH_NODESET) || (argument2->dataType == XPATH_NODESET)) {
		XMLElementList *firstArgument;
		XPathData *secondArgument;
		if (argument1->dataType == XPATH_NODESET) {
			firstArgument = argument1->nodeValue;
			secondArgument = argument2;
		}
		else {
			firstArgument = argument2->nodeValue;
			secondArgument = argument1;
			switch (comparison) {
				case XPATH_LT:
					comparison = XPATH_GTE;
					break;
				case XPATH_GT:
					comparison = XPATH_LTE;
					break;
				case XPATH_LTE:
					comparison = XPATH_GT;
					break;
				case XPATH_GTE:
					comparison = XPATH_LT;
					break;
			}
		}
		int length = firstArgument->length;
		bool found = false;
		XPathData *dummy1, *dummy2;
		for (int i = 0; (i < length) && (!found); i++) {
			char *string = XPath_getText(index, firstArgument->from[i],
					firstArgument->to[i], firstArgument->level[i]);
			switch (secondArgument->dataType) {
				case XPATH_STRING:
					if (XPath_compare(string, secondArgument->stringValue, comparison))
						found = true;
					break;
				case XPATH_NUMBER:
					dummy1 = XPath_createXPathData(index, duplicateString(string));
					dummy2 = XPath_number(dummy1);
					if (XPath_compare(dummy2->numberValue, secondArgument->numberValue, comparison))
						found = true;
					XPath_deleteXPathData(dummy2);
					XPath_deleteXPathData(dummy1);
					break;
				case XPATH_BOOLEAN:
					dummy1 = XPath_createXPathData(index, duplicateString(string));
					dummy2 = XPath_boolean(dummy1);
					if (XPath_compare(dummy2->booleanValue, secondArgument->booleanValue, comparison))
						found = true;
					XPath_deleteXPathData(dummy2);
					XPath_deleteXPathData(dummy1);
					break;
			} // end switch (argument2->dataType)
			free(string);
		}
		result = found;
	} // end if ((argument1->dataType == XPATH_NODESET) || (argument2->dataType == XPATH_NODESET))

	// third type of comparison: "==" and "!=" for non-node-sets
	else if ((comparison == XPATH_EQ) || (comparison == XPATH_NEQ)) {
		if ((argument1->dataType == XPATH_BOOLEAN) || (argument2->dataType == XPATH_BOOLEAN)) {
			XPathData *arg1 = XPath_boolean(argument1);
			XPathData *arg2 = XPath_boolean(argument2);
			result = XPath_compare(arg1->booleanValue, arg2->booleanValue, comparison);
			XPath_deleteXPathData(arg2);
			XPath_deleteXPathData(arg1);
		}
		else if ((argument1->dataType == XPATH_NUMBER) || (argument2->dataType == XPATH_NUMBER)) {
			XPathData *arg1 = XPath_number(argument1);
			XPathData *arg2 = XPath_number(argument2);
			result = XPath_compare(arg1->numberValue, arg2->numberValue, comparison);
			XPath_deleteXPathData(arg2);
			XPath_deleteXPathData(arg1);
		}
		else if ((argument1->dataType == XPATH_STRING) || (argument2->dataType == XPATH_STRING)) {
			XPathData *arg1 = XPath_string(argument1);
			XPathData *arg2 = XPath_string(argument2);
			result = XPath_compare(arg1->stringValue, arg2->stringValue, comparison);
			XPath_deleteXPathData(arg2);
			XPath_deleteXPathData(arg1);
		}
		else
			result = false;
	} // end if ((comparison == XPATH_EQ) || (comparison == XPATH_NEQ))

	// fourth type of comparison: "<=", "<", ">=", ">" on non-node-sets
	else {
		XPathData *arg1 = XPath_number(argument1);
		XPathData *arg2 = XPath_number(argument2);
		result = XPath_compare(arg1->numberValue, arg2->numberValue, comparison);
		XPath_deleteXPathData(arg2);
		XPath_deleteXPathData(arg1);
	}

	return XPath_createXPathData(index, result);
} // end of XPath_compare(XPathData*, XPathData*, int)


bool XPath_compare(XMLElementList *list1, XMLElementList *list2, int comparison) {
	return false;
} // end of XPath_compare(XMLElementList*, XMLElementList*, int)


bool XPath_compare(char *string1, char *string2, int comparison) {
	int result = strcmp(string1, string2);
	switch (comparison) {
		case XPATH_EQ:
			return (result == 0);
		case XPATH_NEQ:
			return (result != 0);
		case XPATH_LT:
			return (result < 0);
		case XPATH_GT:
			return (result > 0);
		case XPATH_LTE:
			return (result <= 0);
		case XPATH_GTE:
			return (result >= 0);
		default:
			return false;
	}
} // end of XPath_compare(char*, char*, int)


bool XPath_compare(bool bool1, bool bool2, int comparison) {
	int value1 = (bool1 ? 1 : 0);
	int value2 = (bool2 ? 1 : 0);
	switch (comparison) {
		case XPATH_EQ:
			return (value1 == value2);
		case XPATH_NEQ:
			return (value1 != value2);
		case XPATH_LT:
			return (value1 < value2);
		case XPATH_GT:
			return (value1 > value2);
		case XPATH_LTE:
			return (value1 <= value2);
		case XPATH_GTE:
			return (value1 >= value2);
		default:
			return false;
	}
} // end of XPath_compare(bool, bool, int)


bool XPath_compare(double number1, double number2, int comparison) {
	switch (comparison) {
		case XPATH_EQ:
			return (fabs(number1 - number2) <= XPATH_EPSILON);
		case XPATH_NEQ:
			return (fabs(number1 - number2) > XPATH_EPSILON);
		case XPATH_LT:
			return (number1 < number2 - XPATH_EPSILON);
		case XPATH_GT:
			return (number1 > number2 + XPATH_EPSILON);
		case XPATH_LTE:
			return (number1 <= number2 + XPATH_EPSILON);
		case XPATH_GTE:
			return (number1 >= number2 - XPATH_EPSILON);
		default:
			return false;
	}
} // end of XPath_compare(double, double, int)




